﻿using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using ParserGenerator.Collections;
using ParserGenerator.DataStructures;
using ParserGenerator.Extensions;
using ParserGenerator.GrammarConstruction;

namespace ParserGenerator.ParserConstruction
{
    [Serializable]
    public sealed class ParserAutomatonGotosTable : ReadOnlyDictionary<GrammarNonterminalSymbol, ParserAutomatonGotos>
    {
        public ReadOnlyCollection<ParserAutomatonGoto> Gotos { get; }
        public ReadOnlyDictionary<ParserAutomatonGoto, ReadOnlySet<GrammarTerminalSymbol>> GotoFollows { get; }
        public ReadOnlyDictionary<ParserAutomatonGoto, ReadOnlySet<GrammarTerminalSymbol>> AlwaysFollows { get; }
        public ReadOnlyDictionary<ParserAutomatonGoto, ReadOnlySet<ParserAutomatonItem>> FollowKernelItems { get; }
        private readonly BinaryRelation<ParserAutomatonGoto> _internalFollowEdges;
        private readonly BinaryRelation<ParserAutomatonGoto> _includeFollowEdges;
        private readonly ReadOnlyDictionary<ParserAutomatonReduction, ReadOnlyCollection<ParserAutomatonGoto>> _lookbackEdges;

        internal ParserAutomatonGotosTable(ParserAutomatonStateTable states)
            : this(states, false)
        {
        }

        internal ParserAutomatonGotosTable(ParserAutomatonStateTable states, bool lookaheadsOnly)
            : base(new Dictionary<GrammarNonterminalSymbol, ParserAutomatonGotos>())
        {
            if (states == null)
                throw new ArgumentNullException(nameof(states));
            int number = 0;
            List<ParserAutomatonGoto> list = new List<ParserAutomatonGoto>();
            foreach (ParserAutomatonState state in states)
            {
                foreach (var t in state.Transitions)
                {
                    if (t.Key.IsTerminal)
                        continue;
                    GrammarNonterminalSymbol symbol = t.Key.AsNonterminal;
                    ParserAutomatonState target = t.Value.Target;
                    ParserAutomatonGoto g = new ParserAutomatonGoto(number++, this, state, symbol, target);
                    ParserAutomatonGotos gotos;
                    if (!Dictionary.TryGetValue(symbol, out gotos))
                    {
                        gotos = new ParserAutomatonGotos();
                        Dictionary.Add(symbol, gotos);
                    }
                    gotos.Add(g);
                    list.Add(g);
                }
            }
            Gotos = list.ToArray().AsReadOnly();
            _internalFollowEdges = new BinaryRelation<ParserAutomatonGoto>();
            _includeFollowEdges = new BinaryRelation<ParserAutomatonGoto>();
            _lookbackEdges = ComputeLookbackEdges();
            AlwaysFollows = ComputeAlwaysFollows(states.Goals);
            GotoFollows = ComputeGotoFollows();
            _includeFollowEdges = null;
            ComputeReductionLookaheadSets(states);
            _lookbackEdges = null;
            if (!lookaheadsOnly)
                FollowKernelItems = ComputeFollowKernelItems(states);
            _internalFollowEdges = null;
        }

        public ParserAutomatonGoto GetGoto(ParserAutomatonState state, GrammarNonterminalSymbol symbol)
        {
            if (state == null)
                throw new ArgumentNullException(nameof(state));
            if (symbol == null)
                throw new ArgumentNullException(nameof(symbol));
            ParserAutomatonGoto g;
            ParserAutomatonGotos gotos;
            if (Dictionary.TryGetValue(symbol, out gotos) && gotos.TryGetValue(state, out g))
                return g;
            string message = string.Format(SR.NoGotoDefinedForStateAndSymbol, state, symbol);
            InvalidOperationException e = new InvalidOperationException(message);
            throw e;
        }

        private ReadOnlyDictionary<ParserAutomatonReduction, ReadOnlyCollection<ParserAutomatonGoto>> ComputeLookbackEdges()
        {
            var lookbackEdges = new Dictionary<ParserAutomatonReduction, List<ParserAutomatonGoto>>();
            foreach (ParserAutomatonGoto g in Gotos)
            {
                foreach (GrammarProduction prod in g.Symbol.Productions)
                {
                    ParserAutomatonItem item = prod.FirstItem;
                    if (item.IsGoto && item.SeesLookaheadSet)
                    {
                        ParserAutomatonGoto g2 = GetGoto(g.State, item.Symbol.AsNonterminal);
                        if (g2 != g)
                            _internalFollowEdges.Add(g2, g);
                    }
                    ParserAutomatonState curState = g.State;
                    while (item.IsRead)
                    {
                        if (item.IsGoto && item.SeesLookaheadSet)
                        {
                            ParserAutomatonGoto g2 = GetGoto(curState, item.Symbol.AsNonterminal);
                            if (g2 != g)
                                _includeFollowEdges.Add(g2, g);
                        }
                        curState = curState.Transitions[item.Symbol];
                        item = item.Successor;
                    }
                    if (!curState.IsConsistent)
                    {
                        ParserAutomatonReduction reduce = curState.GetReduction(item.Production);
                        lookbackEdges.AddValueItem(reduce, g);
                    }
                }
            }
            return lookbackEdges.AsReadOnly();
        }

        private ReadOnlyDictionary<ParserAutomatonGoto, ReadOnlySet<GrammarTerminalSymbol>> ComputeAlwaysFollows(GrammarGoalDescriptorTable goals)
        {
            if (goals == null)
                throw new ArgumentNullException(nameof(goals));
            var alwaysFollows = new Dictionary<ParserAutomatonGoto, HashSet<GrammarTerminalSymbol>>();
            var relation = new BinaryRelation<ParserAutomatonGoto>(_internalFollowEdges);
            foreach (GrammarGoalDescriptor goal in goals.Values)
            {
                ParserAutomatonGoto g = GetGoto(goal.State, goal.GoalSymbol);
                alwaysFollows.AddValueItems(g, goal.EndMarkers);
            }
            foreach (ParserAutomatonGoto g in Gotos)
            {
                ParserAutomatonState state = g.State;
                ParserAutomatonState toState = g.Target;
                foreach (GrammarSymbol sym in toState.Transitions.Keys)
                {
                    if (sym.IsTerminal)
                        alwaysFollows.AddValueItem(g, sym.AsTerminal);
                    else if (sym.Nullable)
                    {
                        ParserAutomatonGoto g2 = GetGoto(toState, sym.AsNonterminal);
                        relation.Add(g, g2);
                    }
                }
            }
            relation.TransitiveClosure(alwaysFollows);
            return alwaysFollows.AsReadOnly();
        }

        private ReadOnlyDictionary<ParserAutomatonGoto, ReadOnlySet<GrammarTerminalSymbol>> ComputeGotoFollows()
        {
            var gotoFollows = new Dictionary<ParserAutomatonGoto, HashSet<GrammarTerminalSymbol>>();
            foreach (var t in AlwaysFollows)
                gotoFollows.Add(t.Key, new HashSet<GrammarTerminalSymbol>(t.Value));
            _includeFollowEdges.TransitiveClosure(gotoFollows);
            return gotoFollows.AsReadOnly();
        }

        private void ComputeReductionLookaheadSets(ParserAutomatonStateTable states)
        {
            if (states == null)
                throw new ArgumentNullException(nameof(states));
            foreach (GrammarGoalDescriptor goal in states.Goals.Values)
            {
                ParserAutomatonState toState = goal.State.Transitions[goal.GoalSymbol];
                if (!toState.IsConsistent)
                {
                    var lookaheadSets = states.ReductionLookaheadSets[toState];
                    var lookaheadSet = lookaheadSets[goal.AcceptProduction];
                    lookaheadSet.UnionWith(goal.EndMarkers);
                }
            }
            foreach (var t in _lookbackEdges)
            {
                foreach (ParserAutomatonGoto g in t.Value)
                {
                    ReadOnlySet<GrammarTerminalSymbol> set;
                    if (GotoFollows.TryGetValue(g, out set))
                    {
                        var lookaheadSets = states.ReductionLookaheadSets[t.Key.State];
                        var lookaheadSet = lookaheadSets[t.Key.Production];
                        lookaheadSet.UnionWith(set);
                    }
                }
            }
        }

        private ReadOnlyDictionary<ParserAutomatonGoto, ReadOnlySet<ParserAutomatonItem>> ComputeFollowKernelItems(ParserAutomatonStateTable states)
        {
            if (states == null)
                throw new ArgumentNullException(nameof(states));
            var followKernelItems = new Dictionary<ParserAutomatonGoto, HashSet<ParserAutomatonItem>>();
            foreach (ParserAutomatonState state in states)
            {
                foreach (ParserAutomatonItem item in state.Core)
                {
                    if (item.IsGoto && item.SeesLookaheadSet)
                    {
                        ParserAutomatonGoto g = GetGoto(state, item.Symbol.AsNonterminal);
                        followKernelItems.AddValueItem(g, item);
                    }
                }
            }
            _internalFollowEdges.TransitiveClosure(followKernelItems);
            return followKernelItems.AsReadOnly();
        }
    }
}
